﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._10
{
    public class Leetcode5
    {
        public void Test()
        {
            try
            {
                string str = "abcabcabc";
                //int startIndex = 8;
                //while (true)
                //{

                //    int i = str.LastIndexOf('a', startIndex);
                //    startIndex=i;
                //}
                LongestPalindrome("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb");
                LongestPalindrome("aaabbaaabbaaa");
            }
            catch (Exception ex)
            { }
        }


        /*
         5. Longest Palindromic Substring
         Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
             */
        public string LongestPalindrome(string s)
        {
            if (s.Length < 3)
                return s;
            string maxPalindromicString = "";
            int maxPalindromicLength = 0;
            char tempChar = ' ';
            int startIndex = 0;
            int endIndex = 0;
            string tempString = "";
            List<char> listChar = new List<char>();
            for (int i = 0; i < s.Length; i++)
            {
                tempChar = s[i];
                if (listChar.Contains(tempChar))
                    continue;
                listChar.Add(tempChar);

                //unique char
                if (s.LastIndexOf(tempChar) == i)
                {
                    continue;
                }
                tempChar = s[i];
                startIndex = s.IndexOf(tempChar, s.IndexOf(tempChar));

                while (maxPalindromicLength < (s.LastIndexOf(tempChar) - startIndex + 1) && startIndex != s.LastIndexOf(tempChar))
                {
                    endIndex = s.LastIndexOf(tempChar);
                    while (endIndex > startIndex)
                    {
                        tempString = s.Substring(startIndex, endIndex - startIndex + 1);
                        if (ComparePalindromic(tempString))
                        {
                            if (tempString.Length > maxPalindromicLength)
                            {
                                maxPalindromicString = tempString;
                                maxPalindromicLength = tempString.Length;
                            }
                            break;
                        }
                        endIndex = s.LastIndexOf(tempChar, endIndex - 1);
                    }

                    if (maxPalindromicLength >= (s.LastIndexOf(tempChar) - startIndex + 1))
                        break;
                    startIndex = s.IndexOf(tempChar, startIndex + 1);
                }
            }


            return maxPalindromicString;
        }

        private bool ComparePalindromic(string str)
        {
            if (str.Length < 2)
                return true;

            int maxLoop = str.Length / 2;
            for (int i = 0; i < maxLoop; i++)
            {
                if (str[i] != str[str.Length - i - 1])
                    return false;
            }

            return true;

        }
    }
}
